//Get the permutation

//time complexity analysis
//the number of permuatations of n numbers is n!, if output of one element is a basic operation, then it needs n*n!
//the number of swaps of elements: n! permutations, at most n-1 swaps from one permutation to another, so <n*n!
//total complexity: O(n*n!)

public class Perm {

	private int cun = 0;
	
	public static void main(String[] args) {
       int[] a = {1,2,3,4};
       Perm mm = new Perm();
       mm.permu(a, 0, a.length-1);
	}

  //	mathematical induction
  //	1.print permutations of a[s]~a[t] with identical leading elements a[0]~a[s-1]
  //	2.a[s]~a[t] remain unchanged between enterance and return of this function
	public void permu(int[] in, int s, int t) {
		if (s == t) {
			for (int i = 0; i <= s; i++) {
				System.out.print(in[i]);				
			}						
			System.out.print(" ");
		} else {
			for (int i = s; i <= t; i++) {
				swap(in, s, i);
				//How to get this induction formulation?
				permu(in, s + 1, t);
				swap(in, i, s);
			}
		}
	}

	private void swap(int[] in, int s, int i) {
		int temp = in[s];
		in[s] = in[i];
		in[i] = temp;
	}
}
